import java.util.Iterator;

public class List implements Iterable<Integer>{
    private  Node hand;

    static class Node {
        public int value;
        public Node next;

        public Node() {
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

    }

    public List() {
        hand = new Node(0,null);
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }


    //头插节点
    public void addFirst(int value) {
        hand.next = new Node(value,hand.next);
    }

    //尾插节点
    public void addLst(int value) {
        Node p = hand;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value,null);
    }


    //根据值来删除节点
    public void removeValue( List list, int value) {
        Node o1 = list.hand;
        Node o2 = list.hand.next;
        while (o2 != null) {

            if (o2.value == value) {
                o1.next = o2.next;
                o2 = o1.next;
            }else {
                o1 = o2;
                o2 = o2.next;
            }
        }

    }

    //根据值来删除节点(递归实现)
    public List removeRecursion(List list ,int value) {
        Node p = list.hand.next;
        Node tp = recursion1(p,value);
        list.hand.next = tp;
        return list;
    }

    private Node recursion1(Node p, int value) {

        if (p == null) {
            return null;
        }
        if (p.value == value) {
            return recursion1(p.next, value);
        }else {
            p.next = recursion1(p.next, value);
            return p;
        }
    }


    //删除倒数第n个节点(递归法)
    public List deleteCount(List list, int n) {
        recursion(list.hand,n);
        return list;
    }

    private int  recursion(Node p, int n) {

        if (p == null) {
            return 0;
        }
        int i = recursion(p.next, n);
        i++;
        if (i == n + 1) {
            p.next = p.next.next;
        }

        return i;
    }


    //删除倒数第n个节点(快慢指针)

    public List removeFastSlowPointers(List list, int n) {
        list.hand = fastSlowPointers(list.hand,n);
        return list;
    }

    private Node fastSlowPointers(Node hand, int n) {
        Node temp = hand;
        Node fast = hand;
        Node slow = hand;
        for (int i = 0; i < n + 1; i++) {
            slow = slow.next;
        }
        while (slow != null) {
            slow = slow.next;
            fast = fast.next;
        }
        fast.next = fast.next.next;
        return temp;
    }

}
